A voxel is a volume element for representing three-dimensional (3D) surface geometry. Voxels are conceptually similar to pixels, but voxels are used to represent objects in a 3D space while pixels are used to represent objects in two-dimensional (2D) images. Voxelization is a process of synthesis of voxel-represented objects, and is a popular technique used in 3D graphics. Voxels are often stored with data that indicates whether the voxel is “on” (e.g., visible) or “off” (e.g., not visible). For example, a designation for a voxel of “on” indicates the presence of solid material, while a designation for the voxel of “off” indicates empty space. Voxels may also contain attributes such as color, texture, a surface normal, or other attribute data.
Like images, a grid of voxels (“voxel grid”) is characterized by its resolution (e.g., a number of voxels in the dimensions of height, width, and depth). The total number of voxels in a grid is the product of the grid's height, width, and depth. The amount of computing memory needed to store a voxel grid is proportional to the total number of voxels in the grid. Accordingly, as the resolution of the voxel grid increases linearly in each dimension, the amount of memory needed to store it grows cubically. This makes using high resolution voxel grids impractical.
One approach is to form a hierarchical tree structure beginning with a root node that corresponds to the entire volume of the voxel grid. The space savings is achieved by eliminating voxels of certain sub-trees. While this approach may reduce the amount of memory needed to represent a voxel grid, the approach requires a large amount of pointer dereferences for random access. This dramatically weakens the value of the approach.